package 题目集.动态规划.背包问题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Map;

/**
 * 记忆化搜索优化枚举版本
 * 一共有n种货物, 背包容量为t。 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出。
 * 请返回选择货物不超过背包容量的情况下，能得到的最大的价值。 测试链接 : https://www.luogu.com.cn/problem/P1776
 * 在完全背包的基础加了每件物品的数量限制。
 */
public class ch09_多重背包1 {
	static int[][] info;
	static int n, sum;

	public static void main(String[] args) {
		Reader sc = new Reader();
		n = sc.nextInt();
		sum = sc.nextInt();
		info = new int[n + 1][3];
		int max=0;
		for (int i = 1; i <= n; i++) {
			info[i][0]=sc.nextInt();
			info[i][1]=sc.nextInt();
			info[i][2]=sc.nextInt();
			max=Math.max(max, info[i][2]);
		}
		dp=new int[n+1][sum+1][max+1];
		int res = dfs(n, sum,info[n][2]);
		System.out.println(res);
	}
	 static int[][][] dp;
	/**
	 * 有i个选择，第i种有count个，容量为sum，能拿走的最大值
	 */
	private static int dfs(int i, int sum,int count) {
		if (i == 0) {
			return 0;
		}
		if(dp[i][sum][count]!=0) {
			return dp[i][sum][count];
		}
		//优化枚举行为
		int chose=0;
		int nochsoe=dfs(i-1,sum,info[i-1][2]);
		if(count!=0&&sum>=info[i][1]) {
			chose=dfs(i,sum-info[i][1],count-1)+ info[i][0];
		}
		dp[i][sum][count]=Math.max(chose, nochsoe);
		return dp[i][sum][count];
	}
//	//不能直接转换为dp
//	public static int dp(int n,int sum,int count) {
//		int[][][] dp=new int[2][sum+1][count+1];
//		int pre,cur=0;
//		
//		for(int i=1;i<=n;i++) {
//			pre=cur;
//			cur=(cur+1)%2;
//			Arrays.fill(dp[cur][0], 0);
//			for(int j=1;j<=sum;j++) {
//				//todo，需要count的信息，而dp[cur][j][count]需要遍历获取
//			}
//		}
//		
//		return dp[cur][sum][info[n][2]];
//	}
	
	static class Reader{
		StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		public int nextInt() {
			try {
				st.nextToken();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return (int) st.nval;
		}
	}
}
